package org.example.myleet.p623;

import org.example.myleet.Utils.TreeNode;

public class Solution {
    public TreeNode addOneRow(TreeNode root, int val, int depth) {
        if (depth == 1) {
            TreeNode newRoot = new TreeNode(val);
            newRoot.left = root;
            return newRoot;
        }
        insert(root, val, depth, 2);
        return root;
    }

    private void insert(TreeNode parent, int val, int depth, int level) {
        if (level >= depth) {
            //left
            TreeNode left = parent.left;
            TreeNode newLeftNode = new TreeNode(val);
            newLeftNode.left = left;
            parent.left = newLeftNode;
            //right
            TreeNode right = parent.right;
            TreeNode newRightNode = new TreeNode(val);
            newRightNode.right = right;
            parent.right = newRightNode;
            return;
        }
        if (null != parent.left) {
            insert(parent.left, val, depth, level + 1);
        }
        if (null != parent.right) {
            insert(parent.right, val, depth, level + 1);
        }
    }
}
